# Jarvis算法
# class Solution(object):
#     def outerTrees(self, trees):
#         node0 = min(trees)
#         start = node0
#         n = len(trees)
#
#         def cmp(a, b, c):
#             v1 = [b[0] - a[0], b[1] - a[1]]
#             v2 = [c[0] - a[0], c[1] - a[1]]
#             ans = v1[0] * v2[1] - v1[1] * v2[0]
#             if ans == 0:
#                 return 0
#             if ans > 0:
#                 return 1
#             else:
#                 return -1
#
#         if n == 1:
#             return trees
#         used = [0] * n
#         while True:
#             flag = False
#             for i in range(n):
#                 if trees[i] != node0:
#                     if not flag:
#                         node1 = trees[i]
#                         node1_list = [i]
#                         flag = True
#                     else:
#                         val = cmp(node0, node1, trees[i])
#                         if val == 1:
#                             node1 = trees[i]
#                             node1_list = [i]
#                         else:
#                             if val == 0:
#                                 node1_list.append(i)
#                                 if abs((trees[i][0] - node0[0]) ** 2 + (trees[i][1] - node0[1]) ** 2) > abs((node1[0] - node0[0]) ** 2 + (node1[1] - node0[1]) ** 2):
#                                     node1 = trees[i]
#             for index in node1_list:
#                 used[index] = 1
#             if node1 == start:
#                 break
#             else:
#                 node0 = node1
#         ans = []
#         for index in range(n):
#             if used[index]:
#                 ans.append(trees[index])
#         return ans

#Grammh算法
# from functools import cmp_to_key
# class Solution(object):
#     def outerTrees(self, trees):
#         n = len(trees)
#         start = min(trees)
#         trees.remove(start)
#         if n == 1:
#             return trees
#
#         def cmp(a, b):
#             v1 = [a[0] - start[0], a[1] - start[1]]
#             v2 = [b[0] - start[0], b[1] - start[1]]
#             val = v1[0] * v2[1] - v1[1] * v2[0]
#             if val > 0:
#                 return -1
#             if val < 0:
#                 return 1
#             if val == 0:
#                 if v1[0] ** 2 + v1[1] ** 2 < v2[0] ** 2 + v2[1] ** 2:
#                     return - 1
#                 else:
#                     return 1
#
#         trees = list(sorted(trees, key=cmp_to_key(cmp)))
#         index = n - 3
#         while index >= 0:
#             v1 = [trees[index][0] - start[0], trees[index][1] - start[1]]
#             v2 = [trees[index + 1][0] - start[0], trees[index + 1][1] - start[1]]
#             if v1[0] * v2[1] - v1[1] * v2[0] == 0:
#                 index -= 1
#             else:
#                 break
#         if index > -1:
#             new_trees = trees[index + 1:]
#             new_trees.reverse()
#             trees = trees[:index + 1] + new_trees
#
#         def guai(a, b, c):
#             v1 = [b[0] - a[0], b[1] - a[1]]
#             v2 = [c[0] - a[0], c[1] - a[1]]
#             val = v1[0] * v2[1] - v1[1] * v2[0]
#             if val >= 0:
#                 return 1
#             else:
#                 return -1
#
#         st = [start, trees[0]]
#         for i in range(1, n - 1):
#             while len(st) >= 2 and guai(st[-2], st[-1], trees[i]) == -1:
#                 st.pop()
#             st.append(trees[i])
#         return st

# Andrew算法
class Solution(object):
    def outerTrees(self, trees):
        n = len(trees)
        if n == 1:
            return trees
        trees.sort()
        def guai(a, b, c):
            v1 = [b[0] - a[0], b[1] - a[1]]
            v2 = [c[0] - a[0], c[1] - a[1]]
            val = v1[0] * v2[1] - v1[1] * v2[0]
            if val == 0:
                return 0
            if val > 0:
                return 1
            else:
                return -1
        used = [0] * n
        used[0] = 1
        used[-1] = 1
        st = [0, 1]
        for i in range(2, n):
            while len(st) >= 2 and guai(trees[st[-2]], trees[st[-1]], trees[i]) == -1:
                st.pop()
            st.append(i)
        for index in st:
            used[index] = 1
        st = [n - 1, n - 2]
        for i in range(n - 3, -1, -1):
            while len(st) >= 2 and guai(trees[st[-2]], trees[st[-1]], trees[i]) == -1:
                st.pop()
            st.append(i)
        for index in st:
            used[index] = 1
        ans = []
        for i in range(n):
            if used[i]:
                ans.append(trees[i])
        return ans

data = Solution()
trees = [[3, 0], [4, 0], [5, 0], [6, 1], [7, 2], [7, 3], [7, 4], [6, 5], [5, 5], [4, 5], [3, 5], [2, 5], [1, 4], [1, 3],
         [1, 2], [2, 1], [4, 2], [0, 3]]
print(data.outerTrees(trees))
# trees = [[1, 5]]\# print(data.outerTrees(trees))
# trees = [[0, 0], [0, 1], [0, 2], [1, 2], [2, 2], [3, 2], [3, 1], [3, 0], [2, 0], [1, 0], [1, 1], [3, 3]]
# print(data.outerTrees(trees))
# trees = [[1, 1], [2, 2], [2, 0], [2, 4], [3, 3], [4, 2]]
# print(data.outerTrees(trees))
